package com.gitee.feizns.explore.data_structure.tree.bs.easy;

import com.gitee.feizns.explore.data_structure.linked_list.singly.ListNode;

/**
 * @author feizns
 * @since 2020/3/9
 */
public class ConvertBiNode {

    public static void main(String[] args) {
        final TreeNode treeNode = new ConvertBiNode().convertBiNode(create());
        System.out.println(treeNode);
    }

    //[-24255,-1416866623,875916498,-1467271685,-935098308,90511200,1650278088,-2006998252,null,-1004522707,-47245,8,553233942,1541934908,1845248881,null,-1758650493,-1175542308,null,-730662,-42710,-406,98402,351943250,796328469,934723866,null,1727747380,2049674601,null,null,-1223928855,-1135520872,-4362279,-185321,null,-25845,-2537,-8,67,2931099,null,522360239,584091166,null,null,1031241928,null,null,null,null,null,null,null,null,-854884265,-3902582,-220260,-76074,-30736,null,-4926,-941,-263,1,47,36111,204993,76546792,null,null,null,null,993616165,null,null,-42580007,null,-1941592,-295887,null,null,-69598,null,null,-24008,null,-1777,-556,null,-218,-4,4,8,66,614,82247,141544,342081,73588469,null,null,null,-324509737,-6389610,null,null,-455311,null,null,-53546,null,null,null,null,-633,null,null,-19,-5,-4,1,6,null,12,null,null,311,861,39984,96404,132075,null,205851,2677726,30693635,null,-543884919,-97455328,-15836765,-4633934,-534555,null,-57079,null,null,null,-73,null,-6,null,null,null,null,3...

    private static TreeNode create() {
        TreeNode r = new TreeNode(0);
        r.left = new TreeNode(-1);
        r.left.left = new TreeNode(-2);
        r.left.left.left = new TreeNode(-3);
        r.left.left.left.left = new TreeNode(-4);
        return r;
    }

    TreeNode pre = new TreeNode(0);
    TreeNode curt = pre;

    public TreeNode convertBiNode2(TreeNode root) {
        inOrder(root);
        return pre.right;
    }

    private void inOrder(TreeNode n) {
        if ( n != null ) {
            inOrder(n.left);
            n.left = null;
            curt.right = n;
            curt = n;
            inOrder(n.right);
        }
    }

    public TreeNode convertBiNode(TreeNode root) {
        if ( root != null ) {
            root.right = convertBiNode(root.right);
            if ( root.left != null ) {
                TreeNode left = convertBiNode(root.left);
                TreeNode node = rightLeaf(left);
                node.right = root;
                root.left = null;
                return left;
            }
        }
        return root;
    }

    private TreeNode rightLeaf(TreeNode n) {
        return n.right != null ? rightLeaf(n.right) : n;
    }

}
